package com.itheima.SensitiveWord;

import java.util.*;

class ACFilter implements SensitiveWordFilter {
    private ACTrie acTrie = null;

    @Override
    public String filter(String text) {
        if (text == null || text.isEmpty()) {
            return text;
        }
        List<MatchResult> match = acTrie.match(text);
        if (match == null || match.isEmpty()) {
            return text;
        }

        // 构建包含敏感词位置和文本信息的字符串
        StringBuilder result = new StringBuilder(text);
        for (MatchResult matchResult : match) {
            result.append("\n敏感词: ").append(matchResult.getSensitiveWord())
                    .append(" 位于: ").append(matchResult.getStartIndex())
                    .append(" - ").append(matchResult.getEndIndex());
        }
        return result.toString();
    }

    @Override
    public boolean hasSensitiveWord(String text) {
        if (text == null || text.isEmpty()) {
            return false;
        }
        return !acTrie.match(text).isEmpty();
    }

    @Override
    public void loadSensitiveWord(List<String> sensitiveWordList) {
        if (sensitiveWordList == null || sensitiveWordList.isEmpty()) {
            return;
        }
        acTrie = new ACTrie(sensitiveWordList);
    }
}

class ACTrie {
    private ACTreeNode root;

    public ACTrie(List<String> words) {
        root = new ACTreeNode();
        for (String word : words) {
            addWord(word);
        }
        initFailover();
    }

    private void initFailover() {
        Queue<ACTreeNode> queue = new LinkedList<>();
        Map<Character, ACTreeNode> children = root.getChildren();
        for (Map.Entry<Character, ACTreeNode> entry : children.entrySet()) {
            ACTreeNode value = entry.getValue();
            value.setFailover(root);
            queue.offer(value);
        }
        while (!queue.isEmpty()) {
            ACTreeNode parentNode = queue.poll();
            for (Map.Entry<Character, ACTreeNode> entry : parentNode.getChildren().entrySet()) {
                ACTreeNode childNode = entry.getValue();
                ACTreeNode failover = parentNode.getFailover();
                while (failover != null &&!failover.hasChild(entry.getKey())) {
                    failover = failover.getFailover();
                }
                if (failover == null) {
                    childNode.setFailover(root);
                } else {
                    childNode.setFailover(failover.childOf(entry.getKey()));
                }
                queue.offer(childNode);
            }
        }
    }

    private void addWord(String word) {
        ACTreeNode wordNode = root;
        char[] words = word.toCharArray();
        for (int i = 0; i < words.length; i++) {
            wordNode.addChildrenIfAbsent(words[i]);
            wordNode = wordNode.childOf(words[i]);
            wordNode.setDepth(i + 1);
        }
        wordNode.setLeaf(true);
    }

    public List<MatchResult> match(String text) {
        List<MatchResult> result = new ArrayList<>();
        ACTreeNode node = root;
        char[] chars = text.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            char aChar = chars[i];
            while (!node.hasChild(aChar) && node.getFailover() != null) {
                node = node.getFailover();
            }
            if (node.hasChild(aChar)) {
                node = node.childOf(aChar);
                if (node.isLeaf()) {
                    int startIndex = i - node.getDepth() + 1;
                    int endIndex = i + 1;
                    String sensitiveWord = text.substring(startIndex, endIndex);
                    result.add(new MatchResult(startIndex, endIndex, sensitiveWord));
                    node = node.getFailover();
                }
            }
        }
        return result;
    }
}

class ACTreeNode {
    private Map<Character, ACTreeNode> children = new HashMap<>();
    private ACTreeNode failover = null;
    private int depth;
    private boolean isLeaf = false;

    public void addChildrenIfAbsent(char c) {
        children.putIfAbsent(c, new ACTreeNode());
    }
    public Map<Character, ACTreeNode> getChildren() {
        return children;
    }

    public ACTreeNode childOf(char c) {
        return children.get(c);
    }

    public boolean hasChild(char c) {
        return children.containsKey(c);
    }

    public void setFailover(ACTreeNode failover) {
        this.failover = failover;
    }

    public ACTreeNode getFailover() {
        return failover;
    }

    public void setDepth(int depth) {
        this.depth = depth;
    }

    public int getDepth() {
        return depth;
    }

    public void setLeaf(boolean leaf) {
        isLeaf = leaf;
    }

    public boolean isLeaf() {
        return isLeaf;
    }

}

class MatchResult {
    private int startIndex;
    private int endIndex;
    private String sensitiveWord;

    public MatchResult(int startIndex, int endIndex, String sensitiveWord) {
        this.startIndex = startIndex;
        this.endIndex = endIndex;
        this.sensitiveWord = sensitiveWord;
    }

    public int getStartIndex() {
        return startIndex;
    }

    public int getEndIndex() {
        return endIndex;
    }

    public String getSensitiveWord() {
        return sensitiveWord;
    }
}

interface SensitiveWordFilter {
    String filter(String text);
    boolean hasSensitiveWord(String text);
    void loadSensitiveWord(List<String> sensitiveWordList);
}